// 0-1背包问题
#include <algorithm>
#include <iostream>
#include <vector>
// 暴力搜索解法
int knap(const std::vector<int> &w, const std::vector<int> &v, int c, int i) {
  if (i == 0 || c == 0) {
    return 0;
  }
  // 当前物品超过背包剩余容量
  if (w[i - 1] > c) {
    return knap(w, v, c, i - 1);
  }
  // 当前物品未超过背包剩余容量
  // 当前物品未放入背包
  int no = knap(w, v, c, i - 1);
  // 当前物品放入背包
  int yes = knap(w, v, c - w[i - 1], i - 1) + v[i - 1];
  return std::max<int>(no, yes);
}

// 记忆化搜索解法
int knap_mem(const std::vector<int> &w, const std::vector<int> &v,
             std::vector<std::vector<int>> &mem, int c, int i) {
  if (i == 0 || c == 0) {
    return 0;
  }
  if (mem[c][i] != -1) {
    return mem[c][i - 1];
  }
  // 当前物品超过背包剩余容量
  if (w[i] > c) {
    return knap_mem(w, v, mem, c, i - 1);
  }
  // 当前物品未超过背包剩余容量
  // 当前物品未放入背包
  int no = knap_mem(w, v, mem, c, i - 1);
  // 当前物品放入背包
  int yes = knap(w, v, c - w[i - 1], i - 1) + v[i - 1];
  mem[c][i] = std::max(no, yes);
  return mem[c][i];
}

// 动态规划解法
/*
到第i个物品时 背包的价值 和 重量
d[i][c] = max(d[i-1][c],d[i-1][c-w[i-1]]) + v[i-1]
*/
int knap_dp(const std::vector<int> &w, const std::vector<int> &v, int cap) {
  int n = w.size();
  // 初始化 dp 表
  std::vector<std::vector<int>> dp(n + 1, std::vector<int>(cap + 1, 0));
  for (int i = 1; i <= n; i++) {
    for (int c = 1; c <= cap; c++) {
      // 背包容量 小于当前物品容量
      if (c < w[i - 1]) {
        dp[i][c] = dp[i - 1][c];
      } else {
        dp[i][c] = std::max(dp[i - 1][c], dp[i - 1][c - w[i - 1]] + v[i - 1]);
      }
    }
  }
  return dp[n][cap];
}

int main() {

  std::vector<int> weights{10, 20, 30, 40, 50};
  std::vector<int> value{50, 120, 150, 210, 240};
  int cap = 50;
  //   int v = knap(weights, value, cap, 5);
  // std::vector<std::vector<int>> mem;
  // mem.resize(cap + 1, std::vector<int>(weights.size(), -1));
  // mem[0][0] = 0;
  // int v = knap_mem(weights, value, mem, cap, weights.size() - 1);
  // std::cout << v << std::endl;
  int v = knap_dp(weights, value, cap);
  std::cout << v << std::endl;
  return 0;
}